/*
* Name        : priority_queue.cpp
* Implementation of priority queue.
* Copyright   :  2013 MIPT-COMPILER team
*/

#include <iostream>
#include <sstream>
#include <vector>

template < class T >
class PQueue
{
    inline std::string toString( const T& t)
    {
        std::stringstream ss;
        ss << t << ' ';
        return ss.str();
    }
    static const int MAX_SIZE = 1000;
    struct Node /*Element of queue*/
    {
        T value;
        int priority;
    };
    std::vector<Node> a; /*queue*/
    int size;
public:
    PQueue()
    {
        size = 0;
    }
    bool add( T, int);
    bool maxPriority( T*);
    void deleteMax();
    std::string serialize();
private:
    static void qswap( Node*, Node*);
    void maxSiftUp( int);
    void heapifyMax();
};

template< class T >
void PQueue<T>::qswap( Node *a, Node *b)
{
    Node tmp = *b;
    *b = *a;
    *a = tmp;
}

template< class T >
void PQueue<T>::maxSiftUp( int i)
{
    int k = (i - 1) / 2;
    while ( a[i].priority > a[k].priority )
    {
        qswap(&a[i], &a[k]);
        i = k;
        k = (i - 1) / 2;
    }
}

template< class T >
void PQueue<T>::heapifyMax()
{
    for ( int i = 0; i < size; ++i )
    {
        maxSiftUp( i);
    }
}

/*
 * Function add element
 * returns true when add was correct
 * returns false when size > MAX_SIZE
 */
template< class T >
bool PQueue<T>::add( T val, int pr)
{
    Node k;
    k.priority = pr;
    k.value = val;
    a.push_back(k);
    ++size;
    heapifyMax();
    return true;
}

/*
 * Function getting element with max priority
 * when queue is empty, function returns false
 * argument of function is variable who uses for getting value
 */
template< class T >
bool PQueue<T>::maxPriority( T* var)
{
    if ( size )
    {
        *var = a[0].value;
        return true;
    } else
    {
        return false;
    }
}

/*
 * Function delete element with max priority
 * when size == 0, function does nothing
 */
template< class T >
void PQueue<T>::deleteMax()
{
    if (size)
    {
        a[0] = a[--size];
        a.pop_back();
        heapifyMax();
    }
}

/*
 * Function convert queue to string
 */
template< class T >
std::string PQueue<T>::serialize()
{
    if ( !size )
    {
        std::string tmp("\0");
        return tmp;
    }
    std::string tmp = toString( a[0].value);
    for ( int i = 1; i < size; ++i )
    {
        tmp = tmp + toString( a[i].value);
    }
    return tmp;
}
